#define _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdbool.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
typedef struct TreeNode
{
	int val;
	struct TreeNode* left;
	struct TreeNode* right;
}BTNode;


int maxDepth(struct TreeNode* root) {
	if (!root)
		return 0;
	if ((root->left == NULL) && (root->right == NULL))
		return 1;

	int LeftDepth = maxDepth(root->left) + 1;
	int RightDepth = maxDepth(root->right) + 1;

	if (LeftDepth > RightDepth)
		return LeftDepth;

	return RightDepth;
}


int gapDepth(struct TreeNode* root)
{
	if (!root)
		return 0;
	int rightDepth = maxDepth(root->left);
	int leftDepth = maxDepth(root->right);

	if (rightDepth > leftDepth)
		return rightDepth - leftDepth;

	return leftDepth - rightDepth;
}

bool isBalanced(struct TreeNode* root)
{
	if (!root)
		return true;
	if (gapDepth(root) > 1)
		return false;

	return isBalanced(root->left) && isBalanced(root->right);
}



BTNode* BinaryTreeCreate(int* a, int* pi)
{
	assert(a);
	if (a[*pi] == 0)
	{
		++(*pi);
		return NULL;
	}

	BTNode* root = NULL;
	BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));
	if (!tmp)
	{
		perror("malloc fail");
		exit(-1);
	}
	tmp->left = tmp->right = NULL;
	root = tmp;
	root->val = a[*pi];
	++(*pi);
	root->left = BinaryTreeCreate(a, pi);
	root->right = BinaryTreeCreate(a, pi);

	return root;
}

int main()
{
	int a[] = { 1,2,4,8,0,0,0,5,0,0,3,6,0,0,0 };
	int i = 0;
	BTNode* root = BinaryTreeCreate(a, &i);
	isBalanced(root);
	return 0;
}